_           _
| |  _   _  | |
| | | |_| | | |
| | |*|*|*| | |
| |_|*|*|*| | |
| | |*|*|*|_| |
|_|_|_|_|_|_|_|
 6 2 5 4 5 1 6
     ^ ^ ^
 0 1 2 3 4 5 6

ÈçͼËùʾ£¬ºÜÖ±¹Û£º3 * 4 == 12.Ê×ÏÈ˼¿¼£¬ÎÒÃÇÊÇÈçºÎµÃµ½×î´óÃæ»ý 12 µÄ£¿

ÎÒÃÇ·¢ÏÖ£¬Òª¼ÆËã Largest Rectangle £¬¹Ø¼üÊÇÕҶ̰壬ÈçÎÒÃÇÌôÑ¡µÄ 4£¬ÀàËƵĻ¹ÓÐÄÄЩÄØ£¿Áиö±í£º

min_height rectangle area
2 0 -> 4 2*5
4 2 -> 4 4*3
1 0 -> 6 1*6

×îÖÕºÜÃ÷ÏÔ£¬area ×î´óµÄ¼´ÎªÖмäÄÇÐУ¬½á¹ûΪ 12.

ÔÙ½øÒ»²½Ë¼¿¼£º

  1. ¶Ì°åÊÇÈçºÎÕª³öÀ´µÄ£¿Õâ¸öºÜÏÔÈ»£¬ÊÇË¥¼õ·¢ÉúµÄʱºò³öÏֵġ£Èç 6->2, 5->4, 5->1.
  2. ¶Ì°åµÄÖÜÆÚÈçºÎµÃ³ö£¿Ï¸Ö¹۲ìºó£¬·¢ÏÖÊǶ̰åÖ®¼äµÄÉý½µ·Ö¸î³öµÄ¡£Èç 2->4:(2), 2->1, 4->1:(4), 2 ºÍ 4 ±ãÊÇ·Ö¸ô·û¡£

ºÃÁË£¬ÏÖÔÚ·¢ÏÖÁ˹æÂÉ£¬µ«ÈçºÎ׼ȷÕÒµ½ËùÐèµÄÊý¾Ý½á¹¹ÄØ£¿

ÎÒÃǵĵÚÒ»¸öÄ¿µÄÏÔÈ»ÊÇÒªÕÒ³ö¶Ì°å£¬¶Ì°åµÄÌõ¼þÊÇ£º

height[i] < height[i-1]

òËƵü´úÒ»±é¼´¿É£¬µ«¶Ì°åµÄÖÜÆÚ·Ö¸ôµãÈçºÎµÃ³öÄØ£¿ÎÒÃDz»½öÒªÕÒ³ö¶Ì°å£¬»¹ÐèÒªÁô϶̰åÒÔ¼°¶Ì°åµÄ index, ÒÔ±ãÑ°ÕÒ·Ö¸ô·û¡£

¿´À´ÎÒÃÇÐèÒªÒ»°Ñɸ×Ó£¬É¸µô²»·ûºÏ¶Ì°åÌõ¼þµÄ£¬Áô϶̰塣

Õ»·Ç³£·ûºÏɸ×ÓµÄÌØÐÔ£¬²»¹ÜÈýÆ߶þʮһ£¬push ½øÈ¥£¬²»·ûºÏÔò pop ³öÀ´¡£

int max_area = 0, i = 0, size = height.size();
for (stack<int> stk; i<size || !stk.empty(); ) { // Õâ¸öµÄ for Ñ­»·ÔÚ¶þ²æÊ÷µÄÌâÄ¿Àï¾­³£³öÏÖ£¨DFS£©
    if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++); // ²»ÊǶ̰壬Ôò push
    else {
        int tp = stk.top(); stk.pop();
        max_area = std::max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));
    }
}

»ù±¾Âß¼­ºÜ¼òµ¥£¬5 ÐнáÊø¡£

#include <vector>
using std::vector;
#include <stack>
using std::stack;
#include <algorithm>
using std::max;

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int max_area = 0, i = 0, size = height.size();
        for (stack<int> stk; i<size || !stk.empty(); )
            if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++);
            else {
                int tp = stk.top(); stk.pop();
                max_area = max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));
            }
        return max_area;
    }
};

LeetCode Direct Link